package main

import "fmt"

/*
	整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 */

/*
当 i >= 2 时，假设对正整数 i 拆分出的第一个正整数是 j（1<j<i），则有以下两种方案：
将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j]。

边界条件 dp[0]以及dp[1]都等于0
 */

func integerBreak(n int) int {
	if n < 2 {
		return 0
	}
	maxNum := func(x, y int) int {
		if x > y {
			return x
		}
		return y
	}
	dp := make([]int, n + 1)
	for i := 2; i <= n; i ++ {
		curNum := 0
		for j := 1; j < i; j ++ {
			curNum = maxNum(curNum, maxNum(j * (i - j), j * dp[i - j]))
		}
		dp[i] = curNum
	}

	return dp[n]
}

func main() {
	fmt.Println(integerBreak(10))
}
